package main.leetcode.clockin.May;

import main.datastruc.ListNode;

/**
 * 25.K个一组翻转链表
 *
 * <p>给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
 *
 * <p>k 是一个正整数，它的值小于或等于链表的长度。
 *
 * <p>如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
 *
 * <p>
 *
 * <p>示例：给你这个链表：1->2->3->4->5
 *
 * <p>当 k = 2 时，应当返回: 2->1->4->3->5
 *
 * <p>当 k = 3 时，应当返回: 3->2->1->4->5
 *
 * <p>
 *
 * <p>说明：你的算法只能使用常数的额外空间。 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class day16 {
    public static void main(String[] args) {
        ListNode node = ListNode.creList(new int[] {1, 2, 3, 4, 5});
        System.out.println(new day16().reverseKGroup(node, 2));
        System.out.println(new day16().reverseKGroup(node, 3));
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || k == 1) {
            return head;
        }
        ListNode tail = head;
        // 找该组k个节点的尾节点
        for (int i = 1; i < k && tail != null; ++i) {
            tail = tail.next;
        }
        // 如果为空，说明长度不够，原顺序返回
        if (tail == null) {
            return head;
        }
        // 记录一下下一组的头结点
        ListNode next = tail.next;
        // 反转该组链表，注意此处反转后，tail成了head，head成了tail
        reverse(head, tail);
        // 连接上下一组的头结点
        head.next = reverseKGroup(next, k);
        return tail;
    }

    // 反转链表
    // 反转链表那题学到的思路，建议去那题跟着走一次，这里的判断条件改了，这个思路真的很妙
    private void reverse(ListNode head, ListNode tail) {
        if (head == tail) {
            return;
        }
        reverse(head.next, tail);
        head.next.next = head;
        head.next = null;
    }
}
